home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8235 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.1 KB
  1. Path: newsroom.hitc.com!usenet
  2. From: psand@eos.hitc.com (G. Patrick Sand)
  3. Newsgroups: comp.lang.c++,
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 15 Feb 1996 22:55:38 GMT
  6. Organization: Hughes Aircraft (EOSDIS)
  7. Message-ID: <4g0dla$hgg@newsroom.hitc.com>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fvp9v$sso@newsroom.hitc.com>
  9. NNTP-Posting-Host: 155.157.118.56
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.99.3
  12.  
  13. In article <4fvp9v$sso@newsroom.hitc.com>, psand@eos.hitc.com says...
  14. >
  15. >In article <31224679.6193@born.com>, clelaj@born.com says...
  16. >>
  17. >>The Crow wrote:
  18. >>> 
  19. >>> Here is what I am trying to do, I want to find the last NON-ZERO digi
  20. >t
  21. >> of a
  22. >>> given factorial.  For instance,
  23. >>> 
  24. >>> 5! = 120
  25. >>> 
  26. >>> so the last non-zero digit is 2.  I want to be able to do this up to 
  27. >1
  28. >>000.
  29. >[SNIP!!!]
  30. >
  31. [SNIP!!!]
  32. >
  33. >If you want to minimize the testing for zero-digits, build yourself a 9x
  34. >9 
  35. >matrix which holds the least-significant digit of the product of 
  36. >(i+1)*(j+1)
  37. >[i,j are C/C++ indexes ranging from 0-8].  You then can use three nested
  38. > 
  39. >for(...) loops and just select the row (new number lsd) and column (lsd 
  40. >of previous factorial) and look it up...
  41. >
  42.  
  43. OKAY, I GOOFED...(Not enough caffeine ;/))  Instead of doing the least
  44. significant digit, take the least significant nonzero digit...
  45.  
  46. so matrix(4,5) = 2  (20 is 4*5, etc...)
  47.  
  48. oooh...I'm feeling a little less brain dead, so here we go:
  49.  
  50.     1  2  3  4  5  6  7  8  9
  51.     -  -  -  -  -  -  -  -  -
  52. 1 | 1  2  3  4  5  6  7  8  9
  53. 2 | 2  4  8  6  1* 2  4  6  8
  54. 3 | 3  6  9  2  5  8  1  4  7
  55. 4 | 4  8  2  6  2* 4  8  2  6
  56. 5 | 5  1* 5  2* 5  3* 5  4* 5
  57. 6 | 6  2  8  4  3* 6  2  8  4
  58. 7 | 7  4  1  8  5  2  9  6  3
  59. 8 | 8  6  4  2  4* 8  6  4  2
  60. 9 | 9  8  7  6  5  4  3  2  1
  61.  
  62. (the * after the number indicates I had to drop a trailing 0)
  63.  
  64. Now all we got to do is take the smallest nonzero digit of the loop 
  65. number,
  66. keep track of the last value found, and look it up (the table is 
  67. symmetric-
  68. multiplicitive commutative stuff)...
  69.  
  70. You know, this could be generalized (using more storage) to do least 
  71. significant nonzero N digits...Of course, once N gets over about 3 you'd 
  72. probably just forget the table...
  73.  
  74. None of the values in the matrix should be zero, so if you use the least 
  75. significant nonzero digit of the loop iterators, you should just have to 
  76. look up a single digit number...
  77.  
  78. By the way, in the generalized case (MOD J), anybody want to tackle 
  79. extending ios to print the values (no fair going hex, decimal, or octal; 
  80. if
  81. you want to do base 2, get a life...)???
  82.  
  83. Hopefully, my braindeath is over...Cute problem...
  84.  
  85. Oh, by the way, the least significant digit for N! base 2 is ONE, when N 
  86. is
  87. 1 or larger; the rest is left as an amusing exercise for the reader...
  88.  
  89. -- 
  90. G. Patrick Sand
  91. psand@eos.hitc.com
  92. PatSand@aol.com
  93. (301) 925-0791
  94. "Travel Light But Right..."
  95. Microsoft Network is prohibited from redistributing 
  96. this work in any form, in whole or in part.   License 
  97. to distribute this individual post is available to Microsoft
  98. for $999. Posting without permission constitutes an 
  99. agreement to these terms...gps
  100.  
  101.